#include<iostream>
#include<string>
#include <utility>
using namespace std;
template <typename A>
class Avlinterval;
template <typename A>
class AvlNode
{
      A data;
      int height;
      AvlNode<A> *leftchild,*rightchild;
      friend class Avlinterval<A>;
};
template <typename A>
class Avlinterval
{
                 public:
                   AvlNode<A> *root;
                   A Ansinterval;
                   bool flag;
                   int count;
                   Avlinterval<A>()
                   {
                                root=NULL;
                                count=0;
                   }
                   AvlNode<A>* insertnode(A data,AvlNode<A> * &root);
                   void display(AvlNode<A> * np);
                   static int Height(AvlNode<A> * np)
                   { if (np==NULL)
                        return -1;
                        else
                        return np->height;}
                   static int Avlinterval<A>::balancefactor(AvlNode<A> *&np)
                   {
                          return Height(np->leftchild)-Height(np->rightchild);
                   }
                   
                   static AvlNode<A>* Avlinterval<A>::leftleft(AvlNode<A> *&K2)
                   {
                          AvlNode<A> *K1;
                          K1 = K2->leftchild;
                          K2->leftchild = K1->rightchild;
                          K1->rightchild = K2;
                          K2->height = Max( Height( K2->leftchild ), Height( K2->rightchild ) ) + 1;
                          K1->height = Max( Height( K1->leftchild ), K2->height ) + 1;
                          return K1; 
                   }
                   static AvlNode<A>* Avlinterval<A>::leftright(AvlNode<A> *&K3){ 
                           K3->leftchild = rightright( K3->leftchild );
                           return leftleft( K3 );
                           }
                   static AvlNode<A>* Avlinterval<A>::rightright(AvlNode<A> *&K1){
                           AvlNode<A> *K2;
                           K2 = K1->rightchild;
                           K1->rightchild = K2->leftchild;
                           K2->leftchild = K1;
                           K1->height = Max( Height( K1->leftchild ), Height( K1->rightchild ) ) + 1;
                           K2->height = Max( Height( K2->rightchild ), K1->height ) + 1;
                           return K2;
                                }
                   static AvlNode<A>* Avlinterval<A>::rightleft(AvlNode<A> *&K1){         
                          K1->rightchild = leftleft( K1->rightchild );
                          return rightright( K1 );
                   }                   
                   
                   static int Max( int Lhs, int Rhs )
                   {return Lhs > Rhs ? Lhs : Rhs;}     
                    
                    bool compareL(A data,AvlNode<A> *&b);             
                    bool compareR(A data,AvlNode<A> *&b);
                   
                   void insert(A k)
                   {
                    root=insertnode(k,root);}
                   bool insert_check(A data,AvlNode<A> *&b);
                   bool CompareIntervalR(A data1,A data2)
                   {
                    if(data2.second<=data1.first)
                                                 return 1;
                   
                    return 0;
                   }     
                   A insertintervalcheck(A k)
                   {
                    if(insert_check(k,root))
                                                return k;
                    else
                        {
                                                flag =false;
                                                insertcheck(k,root);
                        }
                   }
                   
                   void insertcheck(A k,AvlNode<A> *&Parent)
                   { 
                                                                 
                     if(Parent!=NULL&&!flag)
                     {
                              if(!flag)
                                       insertcheck(k,Parent->leftchild);
                              if(!flag)
                              {
                              A temp;
                              temp.first=Parent->data.second;
                              temp.second=temp.first+(k.second-k.first);
                              if(CompareIntervalR(temp,k))                               
                                     if(insert_check(temp,root))
                                                    {           Ansinterval.first=temp.first;
                                                                Ansinterval.second=temp.second;
                                                                flag=true;
                                                    }
                              }
                              if(!flag)
                                       insertcheck(k,Parent->rightchild);
            
                     
                     }
                     
                   }

                   
                   
};

template <typename A>
AvlNode<A>* Avlinterval<A>::insertnode(A data1,AvlNode<A> *&roo)
{
         if(roo==NULL)
         {
                      roo= new AvlNode<A>;
                      roo->data=data1;
                      roo->height=0;
                      roo->leftchild=NULL;
                      roo->rightchild=NULL;
                      count++;
         }
         else if(compareL(data1,roo))
         {
              roo->leftchild=insertnode(data1,roo->leftchild);
              if(balancefactor(roo)==2)
                                       if(balancefactor(roo->leftchild)==1)
                                                                       roo=leftleft(roo);
                                       else
                                           roo=leftright(roo);
         }
         else if(compareR(data1,roo))
              {
                   roo->rightchild=insertnode(data1,roo->rightchild);
                   if(balancefactor(roo)==-2)
                   {
                                                  if(balancefactor(roo->rightchild)==-1)
                                                                roo=rightright(roo);
                                                   else
                                                       roo=rightleft(roo);
                       }
              }
         
         roo->height = Max( Height( roo->leftchild ), Height( roo->rightchild ) ) + 1;
         return roo;
}      

template <typename A>
void Avlinterval<A>::display(AvlNode<A> *T)
{
 if(T!=NULL)
 {
            display(T->leftchild);
            cout<<T->data.first<<" "<<T->data.second<<" "<<"("<<T->height<<")    "<<count<<endl;
            display(T->rightchild);
 }
}

template <typename A>
bool Avlinterval<A>::compareL(A dat,AvlNode<A> *&b)
{
    if(b->data.first>=dat.second)
                                 return 1;
    else 
         return 0;    
    
}
template <typename A>
bool Avlinterval<A>::compareR(A dat,AvlNode<A> *&b)
{
    if(b->data.second<=dat.first)
                                  return 1;
    else
        return 0;
}


template <typename A>
bool Avlinterval<A>::insert_check(A data1,AvlNode<A> *&roo)
{                                             
     if(roo==NULL)
                  return true;
     else if(compareL(data1,roo))
          return insert_check(data1,roo->leftchild);
                
     else if(compareR(data1,roo))
                                 return insert_check(data1,roo->rightchild);
                                 
     return false;
}

                                 

int main()
{
    pair<int,int> b;
    Avlinterval<pair<int,int> > T;
    int i=0,a,ch;
    while(ch!=4)
    {
     cout<<"\nenter your choice 1.insert 2.display 3.insert_check 4.exit";
     cin>>ch;
     switch(ch)
     {
     case 1:
     cout<<"enter the element"<<endl;
     cin>>b.first>>b.second;
     T.insert(b);
     break;
     case 2:
          cout<<"display by postorder traversal"<<endl;
          T.display(T.root);
     break;
     case 3:
          cout<<"Enter interval "<<endl;
          cin>>b.first>>b.second;
          T.insertintervalcheck(b);
          cout<<T.Ansinterval.first<<" "<<T.Ansinterval.second<<endl;
          break;
     } 
    }
    system("pause");
    return 0;
}            


